import java.util.LinkedList;
import java.util.Queue;

/**
 * 1091. 二进制矩阵中的最短路径
 * https://leetcode-cn.com/problems/shortest-path-in-binary-matrix/
 */
public class Solutions_1091 {
    public static void main(String[] args) {
//        int[][] grid = {{0, 0, 0},
//                        {1, 1, 0},
//                        {1, 1, 0}};  // output: 4

//        int[][] grid = {{1, 0, 0},
//                        {1, 1, 0},
//                        {1, 1, 0}};  // output: -1

//        int[][] grid = {{0}};  // output: 1

        int[][] grid = {{0, 0, 1, 0, 0, 0, 0},
                        {0, 1, 0, 0, 0, 0, 1},
                        {0, 0, 1, 0, 1, 0, 0},
                        {0, 0, 0, 1, 1, 1, 0},
                        {1, 0, 0, 1, 1, 0, 0},
                        {1, 1, 1, 1, 1, 0, 1},
                        {0, 0, 1, 0, 0, 0, 0}};  // output: 10

//        int[][] grid = {{0, 1},
//                        {1, 0}};  // output: 2
        int result = shortestPathBinaryMatrix(grid);
        System.out.println(result);
    }

    public static int shortestPathBinaryMatrix(int[][] grid) {
        if (grid == null || grid[0][0] == 1) {
            // 空值，或者起点就是阻塞状态
            return -1;
        }
        int row = grid.length, col = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        // 改变状态，防止扩散时重复访问（取另外的值，不同于0，1）
        grid[0][0] = 2;
        // 初始路径长度为 1
        int res = 1;
        // 八个方向：左上、右上、左下、右下、上、下、左、右
        int[][] direct = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}, {-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                if (cur[0] == row - 1 && cur[1] == col - 1) {
                    // 终点
                    return res;
                }
                // 以 [cur[0], cur[1]] 为原点，向周围八个方向上扩散
                for (int[] dir : direct) {
                    int m = cur[0] + dir[0];
                    int n = cur[1] + dir[1];
                    if (m >= 0 && n >= 0 && m < row && n < col && grid[m][n] == 0) {
                        if (m == row - 1 && n == col - 1) {
                            // 本次扩散，可以扩散到终点
                            return res + 1;
                        }
                        // 本轮扩散到的坐标
                        queue.add(new int[]{m, n});
                        // 改变状态，防止扩散时重复访问（取另外的值，不同于0，1）
                        grid[m][n] = 2;
                    }
                }
            }
            if (queue.isEmpty()) {
                // 剪枝：没有路径可以到达右下角了
                return -1;
            }
            // 向外扩散一层
            res ++;
        }
        return res;
    }
}
